#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void Swap(int* a,int* b){
	int* temp = (int*)malloc( sizeof(int) );
	*temp=*a, *a=*b, *b=*temp;
	free(temp);
	/* *a = *a^*b, *b = *a^*b, *a = *a^*b; */
}

void Sort(int a[],int m,int n){
	int i, j;
	//printf("%d,%d,%d\n",_msize(a)/sizeof(int),sizeof(char*),n);
	for(i=m; i<n; i++){
		for(j=i+1; j<=n; j++){
			if(a[i]>a[j]) Swap(&a[i],&a[j]);
		}
	}
}

void BinarySearch(int a[], int x, int n, int* i, int* j){
	int left = 0, right = n-1;
	int middle;
	while(left<=right){
		middle = (left+right)/2;
		if(x==a[middle]){
			*i = *j = middle;
			return;
		}else if(x>a[middle]){
			left = middle+1;
		}else{
			right = middle-1;
		}
	}
	*i = right+1, *j = left+1;
}

int* add(int *a, int x, int *n, int p){
	int m;
	*n = *n+1;
	a = (int *)realloc( a, (*n)*sizeof(int) );
	for(m=(*n-1); m>p; m--){
		a[m] = a[m-1];
	}
	a[p] = x;
	return a;
}

int main(int argc, char** argv){
	int num = argc-1, i, j, k, search,
	//	*a = (int *)malloc(num*sizeof(int));
		*a = (int *)calloc(num,sizeof(int));

	for(k=1;k<argc;k++) a[k-1] = atoi(argv[k]);

	printf("The input array is: ");
	for(k=0; k<num; k++) printf("%d ",a[k]);
	printf("\n");

	Sort(a,0,num-1);

	printf("The sorted array is: ");
	for(k=0; k<num; k++) printf("%d ",a[k]);
	printf("\n");

	printf("Inputs a number to search:");
	scanf("%d",&search);

	BinarySearch(a,search,num,&i,&j);
	printf("left=%d\nright=%d\n", i, j);

	if(i!=j){
		printf("Not find in the array, Add it in.\nThe result is: ");
		printf("%d\t%d\t%d\n", search, num, i);
		//a = add(a, search, &num, i);
		add(a, search, &num, i);
		for(k=0; k<num; k++){
			printf("%d ", a[k]);
		}
	}else{
		printf("Find it in the array.");
	}
	printf("\n");

	free(a);
	return 0;
}
